1
Modellazione con teoria dei grafi: dal mondo reale alla struttura dati astratta
AI028Lesson 7
00:00

La modellazione con teoria dei grafi è il processo di astrazione delle complesse relazioni di connessione del mondo reale (come il routing su Internet o le transizioni di stato) in un oggetto matematico $G = (V, E)$. Definendo gli enti comenodi (Vertex) e le relazioni comearchi (Edge), possiamo utilizzare un tipo di dato astratto (ADT) e algoritmi standardizzati per risolvere una vasta gamma di problemi.

w=5msw=10msRouter ARouter BInternetMappatura astratta: G = (V, E)

Definizioni dei componenti fondamentali

  • nodi (Vertex): Noti anche come nodi. Possono avere un "chiave" (Key) come identificatore univoco e possono contenere un "payload" (carico utile).
  • archi (Edge): Collega due nodi, indicando che esiste una relazione tra loro. Può essere unidirezionale (grafo orientato) o bidirezionale.
  • Peso (Weight): 边上的数值，代表成本（如距离、延迟、带宽）。

Rigore matematico

Matematicamente, $G = (V, E)$. Dove $V$ è l'insieme dei nodi e $E$ è l'insieme degli archi costituiti da coppie ordinate $(v, w)$, con $v, w \in V$. Questa struttura altamente astratta ci permette di utilizzare lo stesso insieme di algoritmi BFS/DFS per risolvere problemi che vanno dalla navigazione su mappa alla raccomandazione sui social network.

Illuminazione sulla modellazione: grafo dello spazio degli stati
Nella risoluzione di enigmi logici (come il problema dei recipienti), ognistato validoè un nodo, mentre ognioperazione valida则是边。解决问题的过程就是寻找从初始顶点到目标顶点的路径。